import heapq
import math
import random
import time


# 状态压缩DP+二分搜索解法
def exact_min_max_subsequence_sum(nums, k):
    n = len(nums)
    if k > n: return -1
    if k <= 0: return -1
    if k == 1: return sum(nums)

    # 二分搜索范围
    low = max(nums)
    high = sum(nums)

    # 可行性检查函数
    def can_partition(max_sum):
        total_mask = (1 << n) - 1
        # dp[mask] = 当前状态下最后一组的剩余容量
        dp = [-1] * (1 << n)
        # group[mask] = 达到当前状态使用的最小组数
        group = [math.inf] * (1 << n)

        # 初始状态
        dp[0] = 0
        group[0] = 0

        for mask in range(1 << n):
            if dp[mask] == -1:  # 跳过不可达状态
                continue

            for i in range(n):
                if mask & (1 << i):  # 元素i已在当前状态
                    continue

                new_mask = mask | (1 << i)

                # 情况1：将元素i加入当前组
                if dp[mask] >= nums[i]:
                    new_remaining = dp[mask] - nums[i]
                    # 如果新状态未访问过，或能减少组数，或组数相同但剩余容量更大
                    if group[new_mask] > group[mask] or (
                            group[new_mask] == group[mask] and new_remaining > dp[new_mask]):
                        dp[new_mask] = new_remaining
                        group[new_mask] = group[mask]

                # 情况2：为元素i创建新组
                if group[mask] + 1 <= k and nums[i] <= max_sum:
                    new_remaining = max_sum - nums[i]
                    new_group = group[mask] + 1
                    # 如果新状态未访问过，或能减少组数，或组数相同但剩余容量更大
                    if group[new_mask] > new_group or (group[new_mask] == new_group and new_remaining > dp[new_mask]):
                        dp[new_mask] = new_remaining
                        group[new_mask] = new_group

        return group[total_mask] <= k

    # 二分搜索
    while low < high:
        mid = (low + high) // 2
        if can_partition(mid):
            high = mid
        else:
            low = mid + 1

    return low


# 暴力搜索解法（用于小规模数据验证）
def brute_force_min_max_subsequence_sum(nums, k):
    n = len(nums)
    if k > n: return -1
    if k <= 0: return -1
    if k == 1: return sum(nums)

    # 生成所有可能的分组方式
    best = float('inf')

    # 使用递归DFS搜索所有分配方案
    def dfs(index, group_sums, current_max):
        nonlocal best

        # 剪枝：如果当前最大值已经超过已知最优解
        if current_max >= best:
            return

        # 所有元素已分配完毕
        if index == n:
            best = min(best, current_max)
            return

        # 尝试将当前元素分配到每个组
        for i in range(k):
            # 如果当前组是空的，且我们之前已经处理过空组，则跳过
            if group_sums[i] == 0 and any(group_sums[j] == 0 for j in range(i)):
                continue

            # 新和
            new_sum = group_sums[i] + nums[index]
            # 新最大值
            new_max = max(current_max, new_sum)

            # 更新组和
            group_sums[i] = new_sum
            # 递归
            dfs(index + 1, group_sums, new_max)
            # 回溯
            group_sums[i] -= nums[index]

    # 初始化组和
    group_sums = [0] * k
    # 对数组排序（大元素优先）以优化剪枝
    sorted_nums = sorted(nums, reverse=True)
    dfs(0, group_sums, 0)

    return best


# 贪心算法（用于对比）
def greedy_min_max_subsequence_sum(nums, k):
    n = len(nums)
    if k > n: return -1
    if k <= 0: return -1
    if k == 1: return sum(nums)

    nums.sort(reverse=True)
    heap = [0] * k
    heapq.heapify(heap)
    max_sum = 0

    for num in nums:
        current_min = heapq.heappop(heap)
        new_sum = current_min + num
        heapq.heappush(heap, new_sum)
        if new_sum > max_sum:
            max_sum = new_sum

    return max_sum


# 测试用例生成器
def generate_test_case(max_n=10, max_val=100):
    """生成随机测试用例"""
    n = random.randint(1, max_n)
    k = random.randint(1, n)
    nums = [random.randint(1, max_val) for _ in range(n)]
    return nums, k


# 对拍测试
def run_comparison_test(num_tests=100, max_n=10, max_val=100):
    print("开始状态压缩DP+二分搜索 vs 暴力搜索对拍测试...")
    print(f"测试配置: {num_tests}个测试用例, 最大长度={max_n}, 最大值={max_val}")

    passed = 0
    failed = 0
    dp_time_total = 0
    bf_time_total = 0

    for i in range(num_tests):
        nums, k = generate_test_case(max_n, max_val)

        # 运行状态压缩DP+二分搜索
        start = time.time()
        dp_result = exact_min_max_subsequence_sum(nums[:], k)
        dp_time = time.time() - start
        dp_time_total += dp_time

        # 运行暴力搜索
        start = time.time()
        bf_result = brute_force_min_max_subsequence_sum(nums[:], k)
        bf_time = time.time() - start
        bf_time_total += bf_time

        # 比较结果
        if dp_result == bf_result:
            passed += 1
            status = "✓"
        else:
            failed += 1
            status = "❌"
            print(f"\n测试失败 #{i + 1}")
            print(f"输入: nums={nums}, k={k}")
            print(f"状态压缩DP结果: {dp_result}")
            print(f"暴力搜索结果: {bf_result}")

        # 每10个测试打印一次进度
        if (i + 1) % 10 == 0:
            print(f"已完成 {i + 1}/{num_tests} 个测试, 当前状态: {status}")

    print("\n测试结果摘要:")
    print(f"总测试数: {num_tests}")
    print(f"通过: {passed} ({passed / num_tests * 100:.1f}%)")
    print(f"失败: {failed}")
    print(f"状态压缩DP平均用时: {dp_time_total / num_tests * 1000:.2f}ms")
    print(f"暴力搜索平均用时: {bf_time_total / num_tests * 1000:.2f}ms")
    print(f"状态压缩DP总用时: {dp_time_total:.4f}s")
    print(f"暴力搜索总用时: {bf_time_total:.4f}s")

    return passed, failed


# 已知测试用例验证
def run_known_test_cases():
    test_cases = [
        ([10, 8, 7, 5, 2], 2, 17),
        ([6, 5, 4, 3, 2, 1], 3, 7),
        ([1, 1, 1, 1, 1, 1], 3, 2),
        ([30, 20, 10], 2, 30),
        ([900, 800, 700, 600, 500, 400, 300, 200, 100], 3, 1500),
        ([5, 4, 3, 2, 1], 5, 5),
        ([10, 10, 10, 10], 4, 10),
        ([5, 4, 3, 2, 1], 2, 8),
        ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3, 21),
        ([100, 200, 300, 400, 500], 2, 800)
    ]

    print("\n已知测试用例验证:")
    print(f"{'输入':<40} {'k':<5} {'期望':<10} {'状态压缩DP':<10} {'暴力搜索':<10} {'贪心算法':<10}")
    for nums, k, expected in test_cases:
        dp_result = exact_min_max_subsequence_sum(nums, k)
        bf_result = brute_force_min_max_subsequence_sum(nums, k)
        greedy_result = greedy_min_max_subsequence_sum(nums, k)
        status_dp = "✓" if dp_result == expected else f"❌({dp_result})"
        status_bf = "✓" if bf_result == expected else f"❌({bf_result})"
        status_greedy = "✓" if greedy_result == expected else f"❌({greedy_result})"

        print(f"{str(nums):<40} {k:<5} {expected:<10} {status_dp:<10} {status_bf:<10} {status_greedy:<10}")


# 性能对比测试（中等规模数据）
def run_performance_test():
    print("\n性能对比测试（中等规模数据）:")
    sizes = [10, 15, 20]
    k_values = [2, 3, 5]

    for n in sizes:
        for k in k_values:
            if k > n:
                continue

            # 生成测试用例
            nums = [random.randint(1, 1000) for _ in range(n)]

            # 状态压缩DP+二分搜索
            start = time.time()
            dp_result = exact_min_max_subsequence_sum(nums, k)
            dp_time = time.time() - start

            # 暴力搜索（仅当n<=15时运行）
            bf_time = float('inf')
            if n <= 15:
                start = time.time()
                bf_result = brute_force_min_max_subsequence_sum(nums, k)
                bf_time = time.time() - start
            else:
                bf_result = "N/A"

            # 贪心算法
            start = time.time()
            greedy_result = greedy_min_max_subsequence_sum(nums, k)
            greedy_time = time.time() - start

            print(f"n={n}, k={k}:")
            print(f"  状态压缩DP: 结果={dp_result}, 时间={dp_time * 1000:.2f}ms")
            if n <= 15:
                print(f"  暴力搜索:   结果={bf_result}, 时间={bf_time * 1000:.2f}ms")
            print(f"  贪心算法:   结果={greedy_result}, 时间={greedy_time * 1000:.4f}ms")
            print()


if __name__ == "__main__":
    # 运行对拍测试（小规模数据）
    run_comparison_test(num_tests=100, max_n=10, max_val=100)

    # 运行已知测试用例验证
    run_known_test_cases()

    # 运行性能对比测试
    run_performance_test()

    # 测试用例5的详细分析
    print("\n测试用例5详细分析:")
    nums = [900, 800, 700, 600, 500, 400, 300, 200, 100]
    k = 3

    print("输入:", nums)
    print("k:", k)

    # 状态压缩DP+二分搜索
    dp_result = exact_min_max_subsequence_sum(nums, k)
    print("状态压缩DP+二分搜索结果:", dp_result)

    # 暴力搜索
    bf_result = brute_force_min_max_subsequence_sum(nums, k)
    print("暴力搜索结果:", bf_result)

    # 贪心算法
    greedy_result = greedy_min_max_subsequence_sum(nums, k)
    print("贪心算法结果:", greedy_result)

    # 最优划分示例
    print("\n最优划分示例:")
    print("方案1: [900,600] = 1500")
    print("       [800,700] = 1500")
    print("       [500,400,300,200,100] = 1500")
    print("方案2: [900,500,100] = 1500")
    print("       [800,600] = 1400")
    print("       [700,400,300,200] = 1600 (不是最优)")
    print("方案3: [900,400,200] = 1500")
    print("       [800,500,200] = 1500")
    print("       [700,600,300,100] = 1700 (不是最优)")
